package isomorphic.number;
/**
 * @Time 2019/12/21
 * @author 王光浩
 * @Need 给出两个数判断这两个数是否为同构数字，同构数的定义为：（如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
 *               所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。）
 *       Analysis：首先所有出现在S中的字符必须被另个一字符替换，然后字符的顺序要保留（这里的顺序指的是：对于一个字符串来说
 *                 比如说1212类型，则t中字符串也必须是1212类型，如果s中是12345类型，t中就不能是12145类型，就是说你的字母
 *                 可以不同，但是这个字母的排放顺序必须一致。
 * @Thinking 暴力法。使用一个数组来保存s中字符的排列顺序，设置一个双层循环，第一层循环是遍历所有字符，第二层循环是将字符与所有
 *           字符进行比较获取其他相同字符的位置，并在数组的对应位置更改其值（每组相同字符的值不能一致）。然后用同样的方法来获取
 *           保存t中字符串排列顺序的数组，最后将两个数组中的值进行比较，如果全部相等返回true，否则返回false。
 *           复杂度分析：时间复杂度O（n^2），空间复杂度O（n）
 * @Improve 在上面的方法中，我们设置了两个数组，第二个数组用于保存t字符串的字符顺序，但实际上我们可以不必使用到这个数组，
 */
public class MyMethodOne {
    public boolean isIsomorphic(String s, String t) {
    	int sLen=s.length();
    	int tLen=t.length();
    	if(sLen!=tLen)return false;
    	int[] sResult=new int[sLen];    //保存s字符串字符的顺序（注意这里所有值初始都为0）
    	int[] tResult=new int[tLen];
    	int increase=1;                 //对结果数组元素赋值
    	//获取s字符串的顺序
    	for(int i=0;i<sLen-1;i++) {
    		if(sResult[i]!=0) continue; //该字符比较过
    		sResult[i]=increase;
    		for(int j=i+1;j<sLen;j++) {
    			if(s.charAt(i)==s.charAt(j))
    				sResult[j]=sResult[i]; 
    		}
    		increase++;
    	}
    	//获取t字符串的顺序
    	increase=1;
    	for(int i=0;i<sLen-1;i++) {
    		if(tResult[i]!=0) continue; //该字符比较过
    		tResult[i]=increase;
    		for(int j=i+1;j<tLen;j++) {
    			if(t.charAt(i)==t.charAt(j))
    				tResult[j]=tResult[i]; 
    		}
    		increase++;
    	}
    	//将两个结果数组进行比较
    	for(int i=0;i<sLen;i++) {
    		if(sResult[i]!=tResult[i])
    			return false;
    	}
        return true;
    }

}
